package data_structures_and_algorithms.bit_arithmetic;

import java.util.Arrays;

/**
 * @ClassName _56_1_singleNumbers
 * @Description: 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：nums = [4,1,4,6]
 * 输出：[1,6] 或 [6,1]
 * 示例 2：
 *
 * 输入：nums = [1,2,10,4,1,4,3,3]
 * 输出：[2,10] 或 [10,2]
 *  
 *
 * 限制：
 *
 * 2 <= nums.length <= 10000
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Author: yongliang.ma
 * @Create_time:2022/10/11 12:40
 */
public class _56_1_singleNumbers {
    public static void main(String[] args) {
//        int[] nums = new int[]{3,3,4,4,1,6};
        int[] nums = new int[]{1,2,5,2};
        int[] ints = new _56_1_singleNumbers().singleNumbers(nums);
        System.out.println(Arrays.toString(ints));
    }

    public int[] singleNumbers(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            res ^= nums[i];
        }
        int cursor = 1;
        while ((res & cursor) == 0)// 这一步 相与，找到一位两个数字位数不同的值，用于区分两个数
            cursor = cursor << 1;

        int a = 0, b = 0;
        for (int i = 0; i < nums.length; i++) {
            if ((nums[i] & cursor) == 0)// 做与操作，将其他位不同的忽略掉
                a ^= nums[i];
            else
                b ^= nums[i];
        }

        return new int[]{a, b};
    }
}
